package com.shm.leetcode;

import java.util.*;

/**
 * 40. 组合总和 II
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 说明：
 *
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。
 * 示例 1:
 *
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 *   [1, 7],
 *   [1, 2, 5],
 *   [2, 6],
 *   [1, 1, 6]
 * ]
 * 示例 2:
 *
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 *   [1,2,2],
 *   [5]
 * ]
 * @author SHM
 */
public class CombinationSum2 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    /**
     * 一句话题解：按顺序搜索，设置合理的变量，在搜索的过程中判断是否会出现重复集结果。重点理解对输入数组排序的作用和 参考代码 中大剪枝和小剪枝 的意思。
     *
     * 与第 39 题（组合之和）的差别
     * 这道题与上一问的区别在于：
     *
     * 第 39 题：candidates 中的数字可以无限制重复被选取；
     * 第 40 题：candidates 中的每个数字在每个组合中只能使用一次。
     * 相同点是：相同数字列表的不同排列视为一个结果。
     *
     * 如何去掉重复的集合（重点）
     * 为了使得解集不包含重复的组合。有以下 22 种方案：
     *
     * 使用 哈希表 天然的去重功能，但是编码相对复杂；
     * 这里我们使用和第 39 题和第 15 题（三数之和）类似的思路：不重复就需要按 顺序 搜索， 在搜索的过程中检测分支是否会出现重复结果 。注意：这里的顺序不仅仅指数组 candidates 有序，还指按照一定顺序搜索结果。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-3/
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        Set<Integer> set = new HashSet<>();
//        for (int candidate : candidates) {
//            set.add(candidate);
//        }
//        Integer[] ca = new Integer[set.size()];
//        set.toArray(ca);
        Arrays.sort(candidates);
        dfs(candidates,target,0);
        return res;
    }

    public void dfs(int[] ca,int ta,int index){
        if (ta==0){
            res.add(new ArrayList<>(temp));
            return;
        }
//        if (index==ca.length){
//            return;
//        }
        for (int i = index; i < ca.length; i++) {
            /**
             * 解释语句: if cur > begin and candidates[cur-1] == candidates[cur] 是如何避免重复的。
             *
             *
             *
             * 这个避免重复当思想是在是太重要了。
             * 这个方法最重要的作用是，可以让同一层级，不出现相同的元素。即
             *                   1
             *                  / \
             *                 2   2  这种情况不会发生 但是却允许了不同层级之间的重复即：
             *                /     \
             *               5       5
             *                 例2
             *                   1
             *                  /
             *                 2      这种情况确是允许的
             *                /
             *               2
             *
             * 为何会有这种神奇的效果呢？
             * 首先 cur-1 == cur 是用于判定当前元素是否和之前元素相同的语句。这个语句就能砍掉例1。
             * 可是问题来了，如果把所有当前与之前一个元素相同的都砍掉，那么例二的情况也会消失。
             * 因为当第二个2出现的时候，他就和前一个2相同了。
             *
             * 那么如何保留例2呢？
             * 那么就用cur > begin 来避免这种情况，你发现例1中的两个2是处在同一个层级上的，
             * 例2的两个2是处在不同层级上的。
             * 在一个for循环中，所有被遍历到的数都是属于一个层级的。我们要让一个层级中，
             * 必须出现且只出现一个2，那么就放过第一个出现重复的2，但不放过后面出现的2。
             * 第一个出现的2的特点就是 cur == begin. 第二个出现的2 特点是cur > begin.
             */
            if(i > index && ca[i] == ca[i-1]){
                continue;
            }
            if (ta>=ca[i]) {
                temp.add(ca[i]);
                dfs(ca, ta - ca[i], i + 1);
                temp.remove(temp.size() - 1);
            }else{
                break;
            }
        }
    }

    List<int[]> freq = new ArrayList<int[]>();

    /**
     * 在求出组合的过程中就进行去重的操作。我们可以考虑将相同的数放在一起进行处理，也就是说，如果数 \textit{x}x 出现了 yy 次，那么在递归时一次性地处理它们，即分别调用选择 0, 1, \cdots, y0,1,⋯,y 次 xx 的递归函数。这样我们就不会得到重复的组合。具体地：
     *
     * 我们使用一个哈希映射（HashMap）统计数组 \textit{candidates}candidates 中每个数出现的次数。在统计完成之后，我们将结果放入一个列表 \textit{freq}freq 中，方便后续的递归使用。
     *
     * 列表 \textit{freq}freq 的长度即为数组 \textit{candidates}candidates 中不同数的个数。其中的每一项对应着哈希映射中的一个键值对，即某个数以及它出现的次数。
     * 在递归时，对于当前的第 \textit{pos}pos 个数，它的值为 \textit{freq}[\textit{pos}][0]freq[pos][0]，出现的次数为 \textit{freq}[\textit{pos}][1]freq[pos][1]，那么我们可以调用
     *
     * \text{dfs}(\textit{pos}+1, \textit{rest} - i \times \textit{freq}[\textit{pos}][0])
     * dfs(pos+1,rest−i×freq[pos][0])
     *
     * 即我们选择了这个数 ii 次。这里 ii 不能大于这个数出现的次数，并且 i \times \textit{freq}[\textit{pos}][0]i×freq[pos][0] 也不能大于 \textit{rest}rest。同时，我们需要将 ii 个 \textit{freq}[\textit{pos}][0]freq[pos][0] 放入列表中。
     *
     * 这样一来，我们就可以不重复地枚举所有的组合了。
     *
     * 我们还可以进行什么优化（剪枝）呢？一种比较常用的优化方法是，我们将 \textit{freq}freq 根据数从小到大排序，这样我们在递归时会先选择小的数，再选择大的数。这样做的好处是，当我们递归到 \text{dfs}(\textit{pos}, \textit{rest})dfs(pos,rest) 时，如果 \textit{freq}[\textit{pos}][0]freq[pos][0] 已经大于 \textit{rest}rest，那么后面还没有递归到的数也都大于 \textit{rest}rest，这就说明不可能再选择若干个和为 \textit{rest}rest 的数放入列表了。此时，我们就可以直接回溯。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(2^n \times n)O(2
     * n
     *  ×n)，其中 nn 是数组 \textit{candidates}candidates 的长度。在大部分递归 + 回溯的题目中，我们无法给出一个严格的渐进紧界，故这里只分析一个较为宽松的渐进上界。在最坏的情况下，数组中的每个数都不相同，那么列表 \textit{freq}freq 的长度同样为 nn。在递归时，每个位置可以选或不选，如果数组中所有数的和不超过 \textit{target}target，那么 2^n2
     * n
     *   种组合都会被枚举到；在 \textit{target}target 小于数组中所有数的和时，我们并不能解析地算出满足题目要求的组合的数量，但我们知道每得到一个满足要求的组合，需要 O(n)O(n) 的时间将其放入答案中，因此我们将 O(2^n)O(2
     * n
     *  ) 与 O(n)O(n) 相乘，即可估算出一个宽松的时间复杂度上界。
     *
     * 由于 O(2^n \times n)O(2
     * n
     *  ×n) 在渐进意义下大于排序的时间复杂度 O(n \log n)O(nlogn)，因此后者可以忽略不计。
     * 空间复杂度：O(n)O(n)。除了存储答案的数组外，我们需要 O(n)O(n) 的空间存储列表 \textit{freq}freq、递归中存储当前选择的数的列表、以及递归需要的栈。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/combination-sum-ii/solution/zu-he-zong-he-ii-by-leetcode-solution/
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2_1(int[] candidates, int target) {
        Arrays.sort(candidates);
        for (int candidate : candidates) {
            int size = freq.size();
            if (freq.isEmpty() || candidate!=freq.get(size-1)[0]){
                freq.add(new int[]{candidate,1});
            }else {
                ++freq.get(size-1)[1];
            }
        }
        dfs(0,target);
        return res;
    }

    public void dfs(int index,int ta){
        if (ta==0){
            res.add(new ArrayList<>(temp));
            return;
        }
        if (index==freq.size()||ta<freq.get(index)[0]){
            return;
        }
        dfs(index+1,ta);

        int most = Math.min(ta/freq.get(index)[0],freq.get(index)[1]);
        for (int i = 1; i <= most; i++) {
            temp.add(freq.get(index)[0]);
            dfs(index+1,ta-i*freq.get(index)[0]);
        }

        for (int i = 0; i < most; i++) {
            temp.remove(temp.size()-1);
        }
    }

}
